﻿// 花粉化石  FOSSIL.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

/*
https://algospot.com/judge/problem/read/FOSSIL

问题：
每年春天，花粉困扰着过敏症患者，并经常用于追踪过去的气候变化。通过在沉积层中发现的花粉化石，可以确定每个地区的气候如何。业余生物学家 후연绘制了两种不同环境下生长的A和B花朵的花粉发现位置，如下图所示。

hulls-cv.png

在该地图上，y坐标增加表示北方，x坐标增加表示东方。为了预测每种花卉的栖息地，후연计算了包围发现化石位置的最小凸多边形，如上图所示。这些多边形称为凸壳(convex hull)。

후연提出了以下假设：如果两个凸壳有重叠部分，则说明在过去温度变化非常大。为了确定重叠部分的宽度，후연希望找到在南北方向上宽度最大的位置。例如，在上图中，虚线所示的位置的南北方向宽度最大。

给定两个凸壳，请编写一个程序来计算重叠部分的南北最大宽度。

输入：
输入的第一行是测试用例的数量c（c <= 50）。每个测试用例由三行组成。第一行是两个凸壳中包含的点的数量n和m（1 <= n,m <= 100）。接下来一行中，按逆时针顺序给出了第一个凸壳中包含的点的坐标(x,y)，总共有2n个浮点数。然后，下一行以逆时针顺序给出了第二个凸壳中包含的点的坐标(x,y)，总共有2m个浮点数。每个坐标都是范围在[0,100]内的浮点数，小数点后最多保留2位。

在一个测试用例中，不会有重复的点，并且不会出现三个点在同一直线上的情况。所给定的两个多边形的所有内角均小于180度。

输出：
对于每个测试用例，输出一行，其中包含两个凸壳之间重叠部分的南北最大宽度。如果两个凸壳没有重叠，则输出0。答案将被视为正确，如果与实际答案的绝对或相对误差小于10-7。

示例输入：
2
5 5
35.74 35.85 69.64 50.00 73.52 82.55 43.50 92.22 17.67 76.18
16.47 8.02 60.98 14.62 66.80 37.74 45.89 67.22 13.04 55.19
4 3
73.84 11.41 71.61 32.72 39.87 38.84 22.41 17.87
75.13 51.64 47.72 87.34 15.97 64.56

示例输出：
27.6529680365
0.000000
*/
int main()
{
    std::cout << "Hello World!\n";
}

 